﻿#include <iostream>
using namespace std;

// 链表节点类
class Node {
public:
    int data;       // 存储数据
    Node* next;     // 指向下一个节点的指针

    // 构造函数
    Node(int val) : data(val), next(nullptr) {}
};

// 基于链表的队列类
class LinkedListQueue {
private:
    Node* front;    // 指向队列头部的指针
    Node* rear;     // 指向队列尾部的指针

public:
    // 构造函数 - 初始化空队列
    LinkedListQueue() : front(nullptr), rear(nullptr) {}

    // 析构函数 - 释放所有节点内存
    ~LinkedListQueue() {
        while (!isEmpty()) {
            dequeue();// 出队操作 - 移除队首元素
        }
    }

    // 检查队列是否为空
    bool isEmpty() {
        return front == nullptr;  // 如果front为nullptr，队列为空
    }

    // 入队操作 - 在队尾添加元素
    void enqueue(int x) {
        // 创建新节点
        Node* newNode = new Node(x);

        if (isEmpty()) {
            // 如果队列为空，新节点既是队首也是队尾
            front = rear = newNode;
        }
        else {
            // 否则将新节点链接到队尾，并更新rear指针
            rear->next = newNode;
            
            rear = newNode;
        }
    }

    // 出队操作 - 移除队首元素
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty\n";
            return;
        }

        // 保存当前队首节点以便删除
        Node* temp = front;

        // 移动front指针到下一个节点
        front = front->next;

        // 如果队列变为空，也要更新rear指针
        if (front == nullptr) {
            rear = nullptr;
        }

        // 释放原队首节点内存
        delete temp;
    }

    // 获取队首元素（不移除）
    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty\n";
            return -1;  // 返回-1表示错误，实际应用中可能需要其他错误处理方式
        }
        return front->data;
    }

    // 打印队列内容
    void display() {
        if (isEmpty()) {
            cout << "Queue is empty\n";
            return;
        }

        Node* current = front;
        cout << "Queue elements: ";
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

// 测试代码
int main() {
    LinkedListQueue q;

    // 测试入队操作
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();  // 输出: Queue elements: 10 20 30

    // 测试出队操作
    q.dequeue();
    q.display();  // 输出: Queue elements: 20 30

    // 测试获取队首元素
    cout << "Front element: " << q.peek() << endl;  // 输出: Front element: 20

    // 测试队列是否为空
    cout << "Is queue empty? " << (q.isEmpty() ? "Yes" : "No") << endl;  // 输出: No

    // 清空队列
    q.dequeue();
    q.dequeue();
    q.display();  // 输出: Queue is empty

    return 0;
}